555. Ближайшие точки

Антон в школе начал изучать математику. Его внимание привлекло новое для него понятие числовой прямой. Антон быстро научился вычислять расстояния между двумя точками на этой прямой, задавать отрезки и интервалы на ней.

Готовясь к контрольной работе, Антон столкнулся со следующей задачей: На числовой прямой задано n точек. Необходимо найти среди них две ближайшие. Расстояние между двумя точками числовой прямой x и y равно |x – y|.

Требуется написать программу, которая поможет Антону решить поставленную задачу.

Вход. Первая строка содержит количество точек n (2 ≤ n ≤ 10⁵). Вторая строка содержит n различных целых чисел x_i – координаты заданных точек числовой прямой. Числа в строке разделены пробелом. Значение любой координаты x_i не превосходит 10⁹ по абсолютной величине.

Выход. В первой строке следует вывести минимальное расстояние между двумя заданными точками. Во второй строке необходимо вывести номера точек, которым соответствует найденное расстояние. Точки нумеруются натуральными числами от 1 до n в том же порядке, в котором они заданы на входе. Если ответов несколько, выведите любой из них.

Пример входа	Пример выхода
5 10 3 6 2 5	1 2 4

РЕШЕНИЕ

сортировка

Анализ алгоритма

В задаче достаточно отсортировать входные координаты x_i и найти наименьшее значение среди их соседних разностей. При этом необходимо вместе с абсциссой запоминать номер точки. Это можно сделать при помощи вектора пар. Первым элементом пары является абсцисса точки x_i, вторым – ее номер. Точки пронумеруем числами от 1 до n.

Пример

Рассмотрим состояние вектора пар до и после сортировки.

Наименьшее расстояние между соседними элементами массива после сортировки равно 1. Оно достигается, например, между точками 4 и 2, или между точками 5 и 3.

Реализация алгоритма

Объявим вектор пар v, каждый элемент которого v[i] содержит информацию про i-ую точку (абсцисса, номер).

vector<pair<int, int> > v;

Читаем входные данные. Создаем массив точек (точки нумеруются с 1 до n).

scanf("%d",&n);

v.resize(n);

for(i = 0; i < n; i++)

{

scanf("%d",&x);

v[i] = make_pair(x,i+1);

}

Сортируем точки по первому элементу пары, то есть по абсциссе.

sort(v.begin(),v.end());

Находим наименьшее расстояние res между парами соседних точек. В переменных a и b запоминаем номера этих точек.

res = 2e9;

for(i = 1; i < n; i++)

if (v[i].first - v[i-1].first < res)

{

res = v[i].first - v[i-1].first;

a = v[i].second; b = v[i-1].second;

}

Выводим ответ.

printf("%d\n%d %d\n",res,a,b);